﻿\section{XOR (исключающее \IT{ИЛИ})}
\label{XOR_property}

\input{fundamentals/XOR_property_RU}

\subsection{Бытовая речь}

Оперция XOR присутствует в обычной бытовой речи.
Когда кто-то просит ``пожалуйста, купи яблок или бананов'',
это обычно означает ``купи первый объект, или второй, но не оба'' --- это и есть исключающее ИЛИ,
потому что логическое ИЛИ означало бы ``оба объекта тоже сгодятся''.

Некоторые люди предлагают использовать в речи ``и/или'', чтобы подчеркнуть тот факт, что используется именно логическое ИЛИ
вместо исключающего ИЛИ: \url{https://en.wikipedia.org/wiki/And/or}.

\subsection{Шифрование}

Исключающее ИЛИ много используется как в любительской криптографии (\ref{simple_XOR_encryption}), так и в \IT{настоящей}
(как минимум в \IT{сети Фестеля}).

Эта операция очень удобна потому что:
\IT{шифрованный\_текст = исходный\_текст $\oplus$ ключ} и затем:
\IT{(исходный\_текст $\oplus$ ключ) $\oplus$ ключ = исходный\_текст}.

\subsection{\ac{RAID}4}
\index{RAID4}

\ac{RAID}4 предлагает очень простой метод защиты жестких дисков.
Например, есть несколько дисков ($D_1$, $D_2$, $D_3$, итд.) и один диск чётности (\IT{parity disk}) ($P$).
Каждый бит/байт записываемый на диск чётности вычисляется на лету:

\begin{equation} \label{eq:RAID4}
P = D_1 \oplus D_2 \oplus D_3
\end{equation}

Если один из дисков испортился, например, $D_2$, он восстанавливается точно также:

\begin{equation}
D_2 = D_1 \oplus P \oplus D_3
\end{equation}

Если диск чётности испортился, он восстанавливается так же: \ref{eq:RAID4}.
Если два любых диска испортились, тогда уже не получится восстановить оба.

\ac{RAID}5 развился далее, но эта особенность исключающего ИЛИ используется и там.

Вот почему в контроллерах \ac{RAID} были ``XOR-акселлераторы'', они помогали XOR-ить большие объемы данных
на лету, перед записью на диски.
Когда компьютеры стали быстрее, стало возможным делать это же программно, используя \ac{SIMD}.

\subsection{Алгоритм обмена значений при помощи исключающего ИЛИ}

Трудно поверить, но этот код меняет значения в \EAX и \EBX без помощи вспомогательного регистра или ячейки памяти:

\begin{lstlisting}[style=customasmx86]
xor eax, ebx
xor ebx, eax
xor eax, ebx
\end{lstlisting}

Посмотрим, как это работает.
Для начала, мы перепишем этот код, чтобы отойти от ассемблера x86:

\begin{lstlisting}
X = X XOR Y
Y = Y XOR X
X = X XOR Y
\end{lstlisting}

Что содержат X и Y на каждом шаге?
Просто держите в памяти простое правило: $(X \oplus Y) \oplus Y = X$ для любых значений X и Y.

Посмотрим,
$X$ после первого шага это $X \oplus Y$;
$Y$ после второго шага это $Y \oplus (X \oplus Y) = X$;
$X$ после третьего шага это $(X \oplus Y) \oplus X = Y$.

Трудно сказать, стоит ли использовать этот трюк, но он служит неплохой демонстрацией свойств исключающего ИЛИ.

В статье Wikipedia (\url{https://en.wikipedia.org/wiki/XOR_swap_algorithm}) есть еще такое объяснение:
можно использовать сложение и вычитание вместо исключающего ИЛИ:

\begin{lstlisting}
X = X + Y
Y = X - Y
X = X - Y
\end{lstlisting}

Посмотрим:
$X$ после первого шага это $X+Y$;
$Y$ после второго шага это $X+Y-Y=X$;
$X$ после третьего шага это $X+Y-X=Y$.

\subsection{Список связанный при помощи XOR}
\index{Doubly linked list}

Двусвязный список это список, в котором каждый элемент имеет ссылку на предыдущий элемент и на следующий.
Следовательно, легко перечислять элементы и вперед и назад.
\TT{std::list} в Си++ реализует двусвязный список, и он рассматривается в этой книге: \ref{std_list}.

Так что каждый элемент имеет два указателя.
Возможно ли, вероятно, в среде где нужно экономить \ac{RAM}, сохранить всю функциональность используя один указатель
вместо двух?
Да, если будем хранить значение $предыдущий \oplus следующий$ в ячейке, которую обычно называют ``link''.

Можно быть, мы можем сказать, что адрес предыдущего элемента ``зашифрован'' используя адрес следующего элемента и наоборот:
адрес следующего элемента ``зашифрован'' используя адрес предыдущего элемента.

Когда мы проходим по списку вперед, мы всегда знаем адрес предыдущего элемента, так что мы можем ``расшифровать'' это поле
и получить адрес следующего элемента.
Точно также, мы можем пройти по списку назад, ``дешифруя'' это поле используя адрес следующего элемента.

Но невозможно найти адрес предыдущего или следующего элемента определенного элемента без знания адреса первого элемента.

Еще кое-что: первый элемент будем иметь адрес следующего элемента без ничего,
последний элемент будет иметь адрес предыдущего элемента без ничего.

Подведем итоги. Это пример двусвязного списка из 5-и элементов.
$A_x$ это адрес элемента.

\begin{center}
\begin{tabular}{ | l | l | }
	\hline
	\HeaderColor адрес & \HeaderColor содержимое поля \IT{link} \\
	\hline
	$A_0$ & $A_1$ \\
	\hline
	$A_1$ & $A_0 \oplus A_2$ \\
	\hline
	$A_2$ & $A_1 \oplus A_3$ \\
	\hline
	$A_3$ & $A_2 \oplus A_4$ \\
	\hline
	$A_4$ & $A_3$ \\
	\hline
\end{tabular}
\end{center}

И снова, трудно сказать, нужно ли использовать эти хаки, но это также хорошая демонстрация особенностей исключающего ИЛИ.
Как и с алгоритмом обмена значений при помощи исключающего ИЛИ, в статье Wikipedia есть также предложение использовать
сложение или вычитание вместо исключающего ИЛИ:
\url{https://en.wikipedia.org/wiki/XOR_linked_list}.

\subsection{Кстати}

Обычное \IT{ИЛИ} иногда называют \IT{включающее ИЛИ} (\IT{inclusive OR}, или даже \IT{IOR}),
чтобы противопоставить его \IT{исключающему ИЛИ}.

